package pers.qianyu.month_202101.date_20210120;

import pers.qianyu.util.*;
import pers.qianyu.util.model.*;

import java.util.*;

/**
 * 173. 二叉搜索树迭代器
 * https://leetcode-cn.com/problems/binary-search-tree-iterator/
 * - 注意不能定义一个数组作为类的属性，因为题中要求空间复杂度为树的深度
 *
 * @author mizzle rain
 * @date 2021年1月20日17:34:49
 */
public class BSTIterator {
    private Deque<TreeNode> st = new LinkedList<>();

    public BSTIterator(TreeNode node) {
        while (node != null) {
            st.addLast(node);
            node = node.left;
        }
    }

    public int next() {
        TreeNode node = st.pollLast();
        TreeNode p = node.right;
        while (p != null) {
            st.addLast(p);
            p = p.left;
        }
        return node.val;
    }

    public boolean hasNext() {
        return !st.isEmpty();
    }

    public static void main(String[] args) {
        TreeNode root = BinTreeUtil.generateBinTree(new Integer[]
                {7, 3, 15, null, null, 9, 20});
        BSTIterator iter = new BSTIterator(root);
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */